一、題目介紹
本題為LeetCode的Valid Palindrome。
給定一個字串s，判斷它是否為回文（Palindrome）。
判斷時需要：

• 只考慮英文字母與數字
• 忽略大小寫
• 其他符號與空白不需要考慮
  如果從左到右與從右到左讀起來相同，則代表它是回文，回傳true；否則回傳false。

例如：s = "A man, a plan, a canal: Panama"
忽略空白、逗號與冒號，並忽略大小寫後：amanaplanacanalpanama
正反讀取結果相同，因此：true
另一個例子：s = "race a car"
處理後並不是回文，因此：false

二、解題思路
本題可以使用Two Pointers（雙指標）。
建立兩個指標：
left → 從字串最左邊開始
right → 從字串最右邊開始
接著讓兩個指標逐漸向中間移動。

基本流程如下：

1. left指向字串開頭。
2. right指向字串結尾。
3. 如果left指向的字元不是英文字母或數字，就讓left往右移動。
4. 如果right指向的字元不是英文字母或數字，就讓right往左移動。
5. 將兩邊的字元轉換成相同大小寫後進行比較。
6. 如果兩邊不同，代表不是回文，直接回傳false。
7. 如果相同，left向右移、right向左移。
8. 當兩個指標相遇或交錯時，代表檢查完成，回傳true。

三、解題流程
例如：s = "A man, a plan, a canal: Panama"
處理時，可以想像兩個指標從兩端往中間靠近：A → m → a → n → a → ...
... ← a ← m ← A
第一次比較：left = 'A', right = 'a'
忽略大小寫後：'a' == 'a'
所以繼續往中間移動。
遇到：' ' ',' ':'
這些非英數字元時，就跳過它們。
最後所有有效字元都能配對成功，因此回傳：true

核心概念
可以將本題濃縮成：

兩個指標不斷向中央靠近，只需要檢查對應位置的字元是否相同。

四、Java實作

五、Python實作

六、時間與空間複雜度
Java

• Time Complexity：O(n)
  • left與right都只會向中間移動。
  • 每個字元最多被檢查有限次，因此整體為 O(n)。
• Space Complexity：O(1)
  • 只使用left、right等固定數量的變數。
  • 沒有建立額外的字串或陣列。

Python

• Time Complexity：O(n)
  • 使用Two Pointers從兩端向中間走訪字串。
  • 每個字元最多被處理一次。
• Space Complexity：O(1)
  • 沒有建立額外的 List 或其他與輸入大小相關的資料結構。

七、Java與Python解法比較

1. Two Pointers的使用方式
   Java：
   int left = 0;
   int right = s.length() - 1;
   Python：
   left = 0
   right = len(s) - 1
   兩種語言都是讓兩個指標分別從字串兩端開始。

2. 判斷英數字元
   Java：
   Character.isLetterOrDigit(c)
   Python：
   c.isalnum()
   兩者都可以用來判斷字元是否屬於英文字母或數字。

3. 忽略大小寫
   Java：
   Character.toLowerCase(c)
   Python：
   c.lower()
   功能都是將字元轉換成小寫後再進行比較。

4. 資料結構
   本題沒有使用額外的Stack、HashMap或List，而是直接利用原本的String與兩個指標完成判斷。兩者都可以用來判斷字元是否屬於英文字母或數字。
   因此兩種語言都可以維持：
   Time → O(n)
   Space → O(1)
   這也是 Two Pointers 很重要的優點之一。

八、實作結果
LeetCode測試結果：Accepted

九、今日學習心得
今天學習了Two Pointers（雙指標）的基本概念。

與直接建立一個新的字串，再將字串反轉進行比較的方法相比，本題可以直接從字串的兩端開始檢查，讓left與right同時向中間移動。

這讓我了解到，解題時除了考慮「怎麼得到答案」，也可以進一步思考「能不能減少額外使用的空間」。

本題只需要使用兩個指標，就可以完成回文判斷，因此額外空間複雜度為O(1)。

透過今天的練習，我也更加理解Two Pointers的基本概念：

兩個指標從不同方向開始移動，透過縮小搜尋範圍來降低不必要的計算。

這種技巧除了可以應用在回文判斷，也能應用在排序陣列、尋找特定組合等許多問題中。